<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <title>对象数组去重（随机字符串id）</title>
</head>

<body>
<h2>对象数组去重性能测试（id为随机字符串）</h2>
<p>测试数据：800万个对象，每个对象的id是3位随机字符串</p>
<p>各方法去重后长度应相同</p>
<p>方法1嵌套循环和方法4排序后去重的运行太慢，页面容易卡死，不便运行展示</p>
<hr>
<script>

    function getRandomStr(length = 10) {
        const chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789';
        let str = '';
        for (let i = 0; i < length; i++) {
            const randomIndex = Math.floor(Math.random() * chars.length);
            str += chars[randomIndex];
        }
        return str;
    }

    //测试数据
    const objs = [];
    const totalCount = 8_000_000;
    for (let i = 0; i < totalCount; i++) {
        objs.push({
            id: getRandomStr(3), //生成3位随机字符串，字符串太长的话，重复率低
            index: i
        });
    }
    const prop = 'id';

    function showPrint(method, time, len) {
        const p = document.createElement('p');
        p.textContent = `${method}，用时：${(time / 1000).toFixed(3)}s，去重后长度：${len}，原始长度：${totalCount}`;
        document.body.appendChild(p);
    }

    // 方法1：嵌套循环
    function fun1(arr, prop) {
        const start = performance.now();
        const res = [];
        for (let i = 0; i < arr.length; i++) {
            let isRepeat = false;
            for (let j = 0; j < res.length; j++) {
                if (res[j][prop] === arr[i][prop]) {
                    isRepeat = true;
                    break;
                }
            }
            if (!isRepeat) res.push(arr[i]);
        }
        const end = performance.now();
        showPrint(`方法1：嵌套循环【时间复杂度O(n²)】`, end - start, res.length);
        return res;
    }

    // 方法2：Set
    function fun2(arr, prop) {
        const start = performance.now();
        const memory = new Set();
        const res = [];
        arr.forEach(item => {
            const val = item[prop];
            if (!memory.has(val)) {
                memory.add(val);
                res.push(item);
            }
        });
        const end = performance.now();
        showPrint(`方法2：Set【时间复杂度O(n)】`, end - start, res.length);
        return res;
    }

    // 方法3：Map
    function fun3(arr, prop) {
        const start = performance.now();
        const memory = new Map();
        const res = [];
        for (let i = 0; i < arr.length; i++) {
            const val = arr[i][prop];
            if (!memory.has(val)) {
                memory.set(val, true);
                res.push(arr[i]);
            }
        }
        const end = performance.now();
        showPrint(`方法3：Map【时间复杂度O(n)】`, end - start, res.length);
        return res;
    }

    // 方法4：先排序再去重（字符串排序用localeCompare）
    function fun4(arr, prop) {
        const start = performance.now();
        const sorted = [...arr].sort((a, b) => a[prop].localeCompare(b[prop]));
        const res = [];
        let lastVal;
        sorted.forEach(item => {
            const val = item[prop];
            if (val !== lastVal) {
                lastVal = val;
                res.push(item);
            }
        });
        const end = performance.now();
        showPrint(`方法4：先排序再去重`, end - start, res.length);
        return res;
    }

    // 方法5：普通对象作为哈希表
    function fun5(arr, prop) {
        const start = performance.now();
        const memory = {};
        const res = [];
        for (let i = 0; i < arr.length; i++) {
            const val = arr[i][prop];
            if (!memory.hasOwnProperty(val)) {
                memory[val] = true;
                res.push(arr[i]);
            }
        }
        const end = performance.now();
        showPrint(`方法5：普通对象哈希表【时间复杂度O(n)】`, end - start, res.length);
        return res;
    }

    //运行测试
    //fun1(objs, prop);//这个太卡了
    fun2(objs, prop);
    fun3(objs, prop);
    //fun4(objs, prop);
    fun5(objs, prop);
</script>
</body>
</html>